Ch. 19 Big Oh Chart - Worst-case
Big Oh time efficiencies of various methods |
||||||
method |
fixed array |
ArrayList*
|
singly linked list w/ no trailer node |
java.util.LinkedList (implemented as a doubly linked list w/ header & trailer nodes) |
Stack |
Queue |
| java.util.List interface methods | ||||||
| add(Object) | O(n) |
O(n) |
O(1) |
|||
| size | length is
O(1) |
O(1) |
O(n) |
O(n) |
||
| get | [ ] is O(1) |
O(1) |
O(n) |
O(n) |
||
| set | [ ] is O(1) |
O(1) |
O(n) |
O(n) |
||
| java.util.ArrayList methods | ||||||
| add(int, Object) | O(n) |
|||||
| remove | O(n) |
|||||
| LinkedList methods | ||||||
| addFirst | O(1) |
O(1) |
||||
| addLast | O(n) |
O(1) |
||||
| getFirst | O(1) |
O(1) |
||||
| getLast | O(n) |
O(1) |
||||
| removeFirst | O(1) |
O(1) |
||||
| removeLast | O(n) |
O(1) |
||||
| java.util.Stack & java.util.Queue interface methods | ||||||
| isEmpty | O(1) |
O(1) |
||||
| push & add | O(1) |
O(1) |
||||
| pop & remove | O(1) |
O(1) |
||||
| peek | O(1) |
O(1) |
||||
*Since ArrayList is implemented as a "resizable" fixed array, it has some surprising Big Oh evaulations